package com.programmercarl.greed;

/**
 * https://leetcode.cn/problems/maximize-sum-of-array-after-k-negations/
 * K次取反后最大化的数组和 AC
 *
 * @author yulongtian
 * @create 2025-02-07 10:28
 */
public class Test07 {
    public static void main(String[] args) {
        Test07 test07 = new Test07();
        System.out.println(test07.largestSumAfterKNegations(new int[]{2, -3, -1, 5, -4}, 2));
    }

    public int largestSumAfterKNegations(int[] nums, int k) {
        int range = 100;
        int[] cut = new int[range * 2 + 1];
        for (int i = 0; i < nums.length; i++) {
            // -100 0   0 100 100 200
            cut[nums[i] + range]++;
        }
        // 求和
        int ans = 0;
        for (int i = 0; i < nums.length; i++) {
            ans += nums[i];
        }
        for (int i = 0; ; ) {
            if (k == 0) {
                break;
            }
            if (cut[i] == 0) {
                i++;
                continue;
            }
            // i-100 -> 100-i
            // i-100的count - 1
            // 100-i的count + 1
            ans += 2 * (range - i);//和调整  ans - (i-100)+100-i     ans-i+100+100-i
            cut[i]--;
            cut[2 * range - i]++;
            k--;
            i = Math.min(i, 2 * range - i);
            if (i == range) {
                break;
            }
        }
        return ans;
    }

}
